/*
 * @lc app=leetcode.cn id=554 lang=cpp
 *
 * [554] 砖墙
 */

// @lc code=start
class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        //尽可能的多穿过缝隙
        //利用哈希表记录缝隙出现的次数即可
        unordered_map<int, int> hash;
        for(auto &line: wall)
            for(int i = 0, cur = 0; i < (int) line.size() - 1; i++){
                cur += line[i];
                hash[cur] ++;
            }
        
        int maxcnt = 0;
        for(auto [k, v] : hash){
            maxcnt = max(maxcnt, v);
        }
        
        return wall.size() - maxcnt;
    }
};
// @lc code=end

